package leetcode.L146;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    //定义节点
    class DlinkNode{
        int key;
        int value;
        DlinkNode prev;
        DlinkNode next;

        public DlinkNode() {
        }

        public DlinkNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    //定义cache的大小，容量
    private Map<Integer, DlinkNode> cache = new HashMap<>();//hash表用于定位
    private int size;
    private int capacity;
    private DlinkNode head,tail;

    //初始化一个LRUCache的构造方法
    public LRUCache(int capacity) {
        this.size=0;
        this.capacity=capacity;
        head = new DlinkNode();
        tail = new DlinkNode();
        head.next=tail;
        tail.prev=head;
    }

    //get
    public int get(int key) {
        DlinkNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        //若存在，将其移到第一个位置
        moveToHead(node);
        return node.value;
    }

    //put
    public void put(int key,int value) {
        DlinkNode node = cache.get(key);
        if (node == null) {
            DlinkNode newNode = new DlinkNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                DlinkNode tail = removeTail();
                cache.remove(tail.key);//哈希表中也要移除
                size--;
            }
        } else {
            node.value=value;
            moveToHead(node);
        }
    }

    //添加到头节点之后
    private void addToHead(DlinkNode node) {
        node.next=head.next;
        node.prev=head;
        head.next.prev=node;
        head.next=node;
    }

    //删除一个节点
    private void removeNode(DlinkNode node) {
        node.prev.next=node.next;
        node.next.prev=node.prev;
    }

    //移动到头
    private void moveToHead(DlinkNode node) {
        removeNode(node);
        addToHead(node);
    }

    //删除尾部节点返回该节点
    private DlinkNode removeTail() {
        DlinkNode res=tail.prev;
        removeNode(res);
        return res;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */